package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/9 21:57
 */
public class Title210II {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] inDegree = new int[numCourses];
        int count = 0;
        for (int[] dependency : prerequisites) {
            graph.computeIfAbsent(dependency[1], k -> new ArrayList<>()).add(dependency[0]);
            inDegree[dependency[0]]++;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
                count++;
            }
        }
        int index = 0;
        int[] order = new int[numCourses];
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer cur = queue.poll();
                order[index++] = cur;
                List<Integer> orDefault = graph.getOrDefault(cur, new ArrayList<>());
                for (Integer course : orDefault) {
                    inDegree[course]--;
                    if (inDegree[course] == 0) {
                        count++;
                        queue.offer(course);
                    }
                }
            }
        }
        return count == numCourses ? order : new int[]{};
    }

    public static void main(String[] args) {

    }
}
